#include <iostream>
#include <vector>
using namespace std;

struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
void printList(ListNode *head, ListNode *tail) {
  while (head != tail) {
    cout << head->val << " ";
    head = head->next;
  }
  cout << endl;
}

void reverseList(ListNode *&head, int k) {
  cout << "当前处理： " << head->val << endl;
  if (head->next == nullptr) {
    return;
  }
  // [head, tail]之间为需要翻转的数据
  ListNode *tail = head;
  for (int i = 0; i < k - 1; i++) {
    tail = tail->next;
    if (tail == nullptr) {
      return;
    }
  }

  // 保存 下一组链表开始节点指针
  ListNode *nextGropList = tail->next;
  // 该组链表翻转后的头节点指针和尾节点指针
  ListNode *t_sub_head = nullptr, *t_sub_tail = nullptr;
  // 该组链表未翻转前的头节点指针和尾节点指针
  ListNode *t_head = head;
  ListNode *t = nullptr;
  while (t_head != nextGropList) {
    if (t_sub_head == nullptr) {
      t_sub_head = t_sub_tail = t_head;
      t_head = t_head->next;
    } else {
      t = t_sub_head;
      t_sub_head = t_head;
      t_head = t_head->next;
      t_sub_head->next = t;
    }
  }
  head = t_sub_head;
  t_sub_tail->next = nextGropList;
  printList(head, nullptr);
  reverseList(t_sub_tail->next, k);
}

ListNode *reverseKGroup(ListNode *head, int k) {
  reverseList(head, k);
  return head;
}

ListNode *buildLinkedList(const vector<int> &values) {
  ListNode dummy(0); // 创建哑节点作为链表头
  ListNode *current = &dummy;

  for (int val : values) {
    current->next = new ListNode(val);
    current = current->next;
  }

  return dummy.next; // 返回真正的链表头节点
}

int main() {
  vector<int> nums{1, 2, 3, 4, 5};
  ListNode *head = buildLinkedList(nums);
  ListNode *rhead = reverseKGroup(head, 3);
  printList(rhead, nullptr);
  return 0;
}